The present invention relates generally to encoders, particularly priority encoders (priority encoding circuits) and more particularly to a priority encoder for use in acquiring a binary address output by sequentially encoding, in the order of predetermined priorities, a plurality of match address signals in a content addressable memory (CAM) and like, and to an encoder for sequentially efficiently encoding, in the order of predetermined priorities, a plurality of match address signals from a number of blocks in a large capacity content addressable memory and the like.
Heretofore, associative memories, that is, fully parallel CAMs (Content Addressable Memories), have been widely known as semiconductor storage circuits having the functions of performing the match detection of retrieval data and stored data concurrently in terms of all bits and outputting the match address of stored data or stored data (see "Design of CMOS VLSI," pp 176-177, edited by Tetsuya Iizuka and supervised by Takuo Sugano, Baifukan, 1989).
Content-addressed retrieval, instead of retrieval by means of physical memory addresses, is common to content addressable memories (CAMs). Therefore, the basic function of CAM, unlike an ordinary memory, is to input retrieval data so as to output a word address at which data matching the retrieval data has been stored. However, only one word is not necessarily matching and there may be a plurality of them. When the plurality of match words are obtained like this, a correct encode output is unavailable with an ordinary encoder. Consequently, it is necessary to assign a proper priority to a signal before the signal is applied to an ordinary binary encoder so that only one signal is at an ON potential, the signal being sequentially switched to another in synchronization with a clock signal.
For the reason stated above, a priority encoder (priority address encoder) has been employed. Assuming the highest priority is given to an input signal A.sub.3 among those A.sub.3, A.sub.2, A.sub.1, A.sub.0 and the lowest priority is given to A.sub.0 while A.sub.2 and A.sub.1 are in the order of descending priorities in a conventional priority encoder 200 having combinations of invertors 202 and NAND gates 204 as shown in FIG. 16, for example, the encoder outputs the first priority address among addresses at which the input signal is "0" even though a plurality of match signals "0" H (high) are applied as the input signals A.sub.3 -A.sub.0. In other words, the priority encoder 200 is so arranged as to output the address (N, X.sub.1, X.sub.0)=(0, 1, 0) of the first priority input signal A.sub.2 when, for example, A.sub.3 ="0" and A.sub.2 ="0", irrespective of the signal values of lower priority input signals A.sub.1, A.sub.0, that is, even if the value is "0" H (high) (match) or "0" L (low) (mismatch).
Consequently, a truth table is directly used for the NAND gate 204 to accomplish such a priority encoder and even though a plurality of 1's exist in the input signal, the address output of the first priority input signal is obtained. Nevertheless, the circuit becomes increasingly complex in construction as the number of input signals increases and this still poses a critical problem in that a considerable number of elements such as gates are required. In the priority encoder like this, the gates so arranged as to receive lower priority signals are to receive all the signals higher in priority than the former and therefore the NAND gate provided in the portion of the lowest priority input signal is to receive all the input signals. As the number of input signals increases, a multistage gate will be needed because it is impossible to arrange the gates in one stage. Thus, the number of elements sharply increases.
Accordingly, Japanese Patent Publication No. 47038/1990 discloses an priority encoder having a circuit, which is called an priority circuit in the present specification, for defining only the first priority address as 1 out of input signals whose addresses are 1 and for outputting a 0 signal representing an input signal at any other addresses; in other words, a priority assigning portion is separated as a priority circuit, whereas an ordinary address encoder is used to encode a signal (a priority signal) whose only address output therefrom is 1. As shown in FIG. 17, the priority encoder thus disclosed is such that the encoding circuit elements provided for respective signal input terminals are similar in configuration, irrespective of the priority order. With respect to the addresses on one side, that is, those on the lower side in the encoder like this, priority is increased in the descending order.
More specifically, P-channel MOS transistors 212.sub.0, 212.sub.1, 212.sub.2 to be controlled by the input signals applied from respective signal input terminals IN.sub.0, IN.sub.1, IN.sub.2 (the input signals being applied to respective gates) are connected serially in the priority encoder shown in FIG. 17. With a propagation control signal input terminal P.sub.0 in the lowermost part of FIG. 17 as "0" (H), these PMOS transistors 212.sub.0, 212.sub.1, 212.sub.2 are connected transistor-to-transistor (in the preceding stage of each in FIG. 17), by means of the above-noted input signals, to respective N-channel MOS transistors 214.sub.0, 214.sub.1, 214.sub.2 to be exclusively (reversely) controlled, the other end of the terminal being grounded (fixed to "0" L potential). Moreover, there are provided AND gates 216.sub.0, 216.sub.1, 216.sub.2 for ANDing the signals in the following stage of the respective PMOS transistors 212.sub.0, 212.sub.1, 212.sub.2, that is, at the propagation control signal input terminals P.sub.0, P.sub.1, P.sub.2 of the respective encoding circuit elements with the signals of nodes Q.sub.0, Q.sub.1, Q.sub.2 connected via the respective NMOS transistors to the respective signal input terminals IN.sub.0, IN.sub.1, IN.sub.2. The results are output from OUT.sub.0, OUT.sub.1, OUT.sub.2. Even if 1 is applied to the plurality of IN.sub.0, IN.sub.1, IN.sub.2, that is, provided IN.sub.0 ="0", IN.sub.1 =IN.sub.2 ="0", for example, a clock signal C.sub.1 makes the signal state of the nodes Q.sub.0, Q.sub.1, Q.sub.2 respectively (Q.sub.0, Q.sub.1, Q.sub.2)=(0, 1, 1). Thus the PMOS transistors 212.sub.0, 212.sub.1, 212.sub.2 are respectively turned on, off, off; the NMOS transistors 214.sub.0, 214.sub.1, 214.sub.2 are respectively turned off, on, on; and the propagation control signal input terminals (P.sub.0, P.sub.1, P.sub.2)=(1, 1, 0). As a result, the output terminals (OUT.sub.2, OUT.sub.1, OUT.sub.0)=(0, 1, 0), whereby output signals (0, 1, 0) are output. In other words, the output signals (0, 1, 0) with respect to the higher priority IN1="0" are first output.
Subsequently, the nodes (Q.sub.0, Q.sub.1, Q.sub.2)=(0, 0, 1), that is, only the node Q.sub.1 whose output signal is "0" is reset by reset circuits 218.sub.0, 218.sub.1, 218.sub.2 comprising the NMOS transistors for receiving output signals (0, 1, 0) and its output signal turns from "0" to "0". Consequently, the PMOS transistor 212.sub.1 is turned on from the off state, whereas the NMOS transistor 214.sub.1 is turned off from the on state. In other words, the propagation control signal "0" is propagated up to the terminal P.sub.2 and therefore the propagation control signal input terminal P.sub.2 =1, whereas output terminals (OUT.sub.2, OUT.sub.1, OUT.sub.0)=(1, 0, 0), whereby the output signal (1, 0, 0) is applied to IN.sub.2 ="0" having the second priority. Even when the plurality of "1"s are applied to the signal input terminals IN.sub.0, IN.sub.1, IN.sub.2, the selection of each located below is given the first priority and only one of the output terminals OUT.sub.0, OUT.sub.1, OUT.sub.2 sequentially outputs a signal of "0". In this case, the output signals (0, 1, 0) and (1, 0, 0) whose only one address is 1 are encoded by the conventional address encoder 220 as shown in FIG. 15, for example. Even when the number of inputs increases further, entirely similar priority circuit elements are additionally provided so as to cause the same operation to be performed.
The priority circuit of FIG. 17 has the priority circuit elements which are equally uniform in configuration and even if these elements in combination with the conventional address encoder 220 of FIG. 15 are used as a priority encoder, this priority encoder has less elements but operates at relatively high speed as compared with the priority encoder of FIG. 16, particularly when the number of inputs is small. If, however, the number of inputs to a large capacity CAM increases, as many priority circuit elements stated above as the inputs required are connected to the CAM. Since it is necessary for the priority-determining propagation control signal to be transmitted correspondingly through the PMOS transistors serially connected from bottom to top, the output signal with only one address as 1 is output as the number of inputs increases and the priority delays varying after the output is reset by the reset circuits 218 using the output itself. The problem is that it takes time until the second priority signal is output.
As set forth above, CAM employs the priority encoding circuit (priority encoder) for encoding and outputting the plurality of match signals (hit signals) in the order of predetermined priorities.
In a large capacity CAM, however, the number of words is generally very large in contrast to the word length. For this reason, a cell array is divided into a plurality of blocks and it is an important problem how priority encoders are arranged. In other words, the priority encoders will occupy a large area and power consumption will also be on the increase if the priority encoder is provided for every block of CAM. As the number of blocks increases because of the division of the array, the area thus occupied thereby and the power consumption proportionally increase further.
As a result, there has been proposed a content addressable memory in which one main priority encoder is provided for the plurality of blocks and a block priority encoder to be separately provided is used for the block in which encoding is carried out by the main priority encoder.
FIG. 18 shows such a content addressable memory (CAM). As shown in FIG. 18, the content addressable memory 240 is divided into four CAM blocks 242 and each CAM block 242 is further divided into eight CAM subblocks 244. A priority encoder 250 is structurally hierarchical in that there are installed four main priority encoders 252, each being for the CAM block 242 having eight of the CAM subblocks 244, and one subblock priority encoder 254 is provided every four CAM blocks. As shown in FIG. 19 further, the CAM subblock 244 comprises a CAM subarray 246 having a predetermined number of CAM words with predetermined word length and its control unit including a hit signal register 248 for holding a hit signal resulting from the hitting of retrieval data against a CAM word.
At the time of match retrieval in the CAM block 242, the hit signals of all words in each subblock 244 are held by the hit signal register 248 and a subblock hit signal indicating the presence of a match word in the subblock 244 is simultaneously generated by an OR circuit (not shown) of the control unit in each CAM block 244. On receiving the signal, the subblock priority encoder 254 subsequently generates a subblock selection signal indicating the first priority CAM subblock 244 and the subblock priority encoder 254 also generates an encoded subblock address. On receiving the block selection signal, a switch circuit (not shown) of the subblock thus selected is then activated to transfer the data (hit signal) held in the hit signal register 248 to the main priority encoder 252 as an output signal. Thereafter, the main priority encoder 252 generates a hit memory word address resulting from the hit signal thus transferred and encoded in the order of predetermined priorities in the CAM block 244. The priority encoder 250 combines the hit memory word address and the aforementioned subblock address and outputs the encoding logical address of the hit memory word of the CAM.
In the conventional CAM memory 240 shown in FIGS. 18 and 19, the priority encoder (encode circuit) 250 comprises the main priority encoder (priority encode circuit) for controlling the plurality of CAM subblocks 244 and the subblock priority encoder 254 for assigning priority to the CAM subblocks 244 for encoding purposes. The order of priorities is first determined among the plurality of the subblocks 244 and before being encoded, the output signal of the first priority subblock 244 is applied to the main priority encoder 252. The encode circuit can be made relatively small in configuration, whereas the circuit area relative to the whole circuit scale of the CAM memory 240 is reduced, whereby large scale integration is made possible.
Notwithstanding, subblock-to-subblock switch time becomes necessary when the output signal (hit signal data) from the second priority CAM subblock 244 is encoded after the output signal (hit signal data) from the first priority subblock 244 is encoded by the main priority encoder 252 and output. In other words, it takes time to transfer the hit signal data from the hit signal register 248 of the second priority subblock after an encoded address is output from the main priority encoder 252 and there still arises a problem of making an efficient encoding operation unfeasible.